package daily.oct;

import java.util.*;

public class lc3186 {
    public long maximumTotalDamage(int[] power) {
        //Arrays.sort(power);
        //interger:魔法的power（数值）    Long:魔法的总伤害（power*count）
        TreeMap<Integer, Long> map = new TreeMap<>();//treemap按顺序录入键值对，并且天然具有排序去重效果

        for (int i:power) {
            map.put(i,map.getOrDefault(i,0L)+i);
        }

        int len = map.size();
        int[] uniquePower =new int[len];
        long[] totalDamage=new long[len];
        int idx=0;
        for (Map.Entry<Integer, Long> entry:map.entrySet()) {
            uniquePower[idx]=entry.getKey();
            totalDamage[idx]=entry.getValue();
            idx++;
        }

        long[] dp = new long[len];
        dp[0] = totalDamage[0];

        for (int i = 1; i < len; i++) {
            //不选择当前魔法
            dp[i]=dp[i-1];

            //选择当前魔法
            int current=uniquePower[i];
            int j=i-1;
            while (j>=0 && current-uniquePower[j]<=2) {//此时不满足条件，索引j处的unique太大，减小j索引值
                j--;
            }

            if (j>=0) {
                dp[i]=Math.max(dp[i], dp[j]+totalDamage[i]);
            }else  {
                // 前面没有不冲突的伤害值，只能单独选当前伤害值
                dp[i]=Math.max(dp[i],totalDamage[i]);
            }
        }

        return dp[len-1];
    }

    public static void main(String[] args) {
        lc3186 lc = new lc3186();
        int[] power={1,1,3,4};
        System.out.println(lc.maximumTotalDamage(power));

    }
}
